import java.util.*;
/**
 * Created by L.jp
 * Description:其实前序数组的每一个节点在中序数组中的位置，我们可以利用哈希表把它们映射起来，
 *  * 这样就不用进行下标换算，构建二叉树的时候我们采用另外一种方法，不使用Arrays.copyOfRange函数
 *  * 直接利用在哈希表里面存好的下标进行计算，得到右视图的时候我们还是利用队列存储层次遍历的每一层节点
 *  * 直到每一层的队列的大小为0的时候，弹出的节点就是最右边的节点
 * User: 86189
 * Date: 2022-06-30
 * Time: 16:34
 */
public class Solution3 {
    Map<Integer,Integer> map=null;
    //四个int参数分别是先序最左节点下标，先序最右节点下标
    //中序最左节点下标，中序最右节点坐标
    //不借助哈希表构建二叉树的版本
    public TreeNode reBuild(int[] pre,int ps,int pe,int[] vin,
                            int vs,int ve) {
        if ( ps > pe || vs > ve ) {
            return null;
        }
        //前序遍历中的第⼀个节点就是根节点
        int preRoot = ps;
        //直接利用哈希表来得到先序数组根节点在中序数组中的位置
        int vinRoot = map.get( pre[preRoot] );
        TreeNode root = new TreeNode( pre[preRoot] );
        //得到左子树的个数
        int leftSize = vinRoot - vs;
        root.left = reBuild( pre , ps + 1 , ps + leftSize ,
                vin , vs , vinRoot - 1 );
        root.right = reBuild( pre , ps + leftSize + 1 , pe ,
                vin , vinRoot + 1 , ve );
        return root;
    }
    //存储右视图
    public ArrayList<Integer> getRightView(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        ArrayList<Integer> list=new ArrayList<>();
        queue.add( root );
        TreeNode cur=null;
        while ( !queue.isEmpty() ){
            //队列的大小就是这一层的节点个数
            int size=queue.size();
            while (size--!=0) {
                cur=queue.poll();
                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                }
            }
            list.add(cur.val);
        }
        return list;
    }
    public int[] solve (int[] xianxu, int[] zhongxu) {
        map=new HashMap<>();
        if(xianxu.length==0){
            return new int[0];
        }
        //哈希表存储先序数组的节点在中序数组的位置
        for(int i = 0; i < xianxu.length; i++){
            map.put(zhongxu[i], i);
        }
        //构建二叉树
        TreeNode root=reBuild( xianxu,0, xianxu.length-1,
                               zhongxu,0, zhongxu.length-1);
        //取出右视图
        ArrayList<Integer> list=getRightView( root );
        int[] ret=new int[list.size()];
        for(int i = 0; i <list.size(); i++){
            ret[i] = list.get(i);
        }
        return ret;
    }

}
